class Solution
{
public:
    int minTaps(int n, vector<int> &ranges)
    {
        unordered_map<int, int> maxReach;
        for (int i = 0; i <= n; ++i)
        {
            int beginPos = i - ranges[i];
            int endPos = i + ranges[i];
            beginPos = max(0, beginPos);
            endPos = min(n, endPos);
            maxReach[beginPos] = max(maxReach[beginPos], endPos);
        }
        int tapCount = 0;
        int reach = 0;
        int nextReach = 0;
        int farReach = 0;
        while (reach < n)
        {
            farReach = max(farReach, maxReach[reach]);
            if (farReach == reach)
            {
                return -1;
            }
            if (reach == nextReach)
            {
                nextReach = farReach;
                ++tapCount;
            }
            ++reach;
        }
        return tapCount;
    }
};